/**
 * 线性表中的元素递增有序，设计一个算法在最短的时间内查找数值为x的元素，
 * 若找到，则将其与后继元素位置交换；若找不到，则将其插入表中使得线性表仍然递增有序
 */

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 50		// 线性表的最大长度
#define ElemType int    // 元素存储类型
#define bool int
#define true !0
#define false 0

typedef struct {
	ElemType data[MAX_SIZE];
	int length;			// 顺序表当前长度
} SqList;

void SearchExchangeInsert(SqList& L, ElemType x)
{
	int low=0, high=L.length-1, mid;
	while(low <= high)
	{
		mid=(low+high)/2;
		if(L.data[mid] == x) break;
		else if(L.data[mid] < x) low = mid + 1;
		else high = mid - 1;
	}
	
	//找到了与x相等的元素，且不是最后一个元素
	if(L.data[mid] == x && mid != L.length - 1) {
		int t = L.data[mid];
		L.data[mid] = L.data[mid+1];
		L.data[mid+1] = t;
	}
	//并没有找到，则找到合适的位置插入
	if(low > high) {
		int i;
		for(int i=L.length-1; i>high; i--) L.data[i+1] = L.data[i];//腾出位置向后移动
		L.data[i+1] = x;
	}
}
